﻿#include<iostream>
#include<map>
#include<string>
using namespace std;


//template <class T1, class T2>
//struct pair
//{
//	//默认构造
//	pair() : first(T1()), second(T2())
//	{}
//	//带参构造
//	pair(const T1& a, const T2& b) : first(a), second(b)
//	{}
//	//泛化的拷贝构造函数
//	template<class U, class V>
//	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
//	{}
//
//	//类型重定义
//	typedef T1 first_type;
//	typedef T2 second_type;
//	//成员变量
//	T1 first;
//	T2 second;
//};
//
////typedef pair<const Key, T> value_type;
//
//
//int main()
//{
//
//	return 0;
//}
//
//map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };
//
//
//// 范围for遍历
//for (const auto& e : dict)
//{
//	cout << e.first << ":" << e.second << endl;
//}
//cout << endl;


//int main()
//{
//	// 利⽤find和iterator修改功能，统计⽔果出现的次数
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//
//	for (auto e : arr)
//	{
//		//auto it = countMap.find(e);
//		//if (it == countMap.end())
//		//{
//		//	countMap.insert({e, 1});
//		//}
//		//else
//		//{
//		//	it->second++;
//		//}
//		countMap[e]++;
//	}
//
//	for (const auto& e : countMap)
//    {
//	    cout << e.first << ":" << e.second << endl;
//    }
//    cout << endl;
//
//
//	//V& operator[](const K& key)
//	//{
//	//	pair<iterator, bool> ret = insert({ key, V() });
//	//	//ret.first返回key所在的迭代器，然后->second返回key所在迭代器里的value
//	//	return ret.first->second; 
//	//}
//
//	map<string, string> dict;
//	//插入
//	dict["left"];
//	//插入+修改
//	dict["right"] = "右边";
//	//修改
//	dict["left"] = "左边";
//	//查询
//	cout << dict["left"] << endl;
//	return 0;
//}


// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

int main()
{
    map<Node*, Node*> nodeMap;
    Node* cur = head;
    Node* copyhead = nullptr;
    Node* copytail = nullptr;
    //拷贝原链表+建立映射关系
    while (cur != nullptr)
    {
        //拷贝第一个结点
        if (copyhead == nullptr)
        {
            copyhead = copytail = new Node(cur->val);
        }
        else
        {
            copytail->next = new Node(cur->val);
            copytail = copytail->next;
        }
        //key:cur value:copytail
        nodeMap[cur] = copytail;
        cur = cur->next;
    }
    //处理拷贝链表的random
    //
    cur = head;
    Node* copycur = copyhead;
    while (cur != nullptr)
    {
        if (cur->random == nullptr)
        {
            copycur->random = nullptr;
        }
        else
        {
            copycur->random = nodeMap[cur->random];
        }
        cur = cur->next;
        copycur = copycur->next;
    }
}


class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countmap;
        for (auto& e : words)
        {
            countmap[e]++;
        }

        priority_queue<int> q;
        for (auto& e : countmap)
        {
            q.push(e.second);
        }

        vector<string> rv;
        while (k--)
        {
            rv.push_back(q.top());
            q.pop();
        }
        return rv;
    }
};



